package com.algorithm.middleware.LRU;

import java.util.HashMap;

/**
 * @author liyanhao
 * @Date 2023-02-12 18:08
 * laest recently Used 最近最少使用算法
 * LRU(最近最少使用)缓存机制要求支持以下操作 获取数据get和写入数据get
 * 获取数据get(key) 如果秘钥key存在于缓存中，则获取秘钥的值，否则返回-1
 * 写入数据put(key,value) 如果秘钥不存在 则写入数据值 当缓存容量达到上限时，
 * 他应该在写入新数据之前删除最久未使用的数据值，从为新的数据值流出空间
 * 在o(1)时间复杂度内完成这两种操作
 *
 * get(key)速度快考虑hashMap操作
 * 算法要求当缓存达到容量是，可以删除最近最少使用的项，那么对于每一组kv对象，都
 * 考虑放到一个双向链表中，每对一个kv对操作时，都应该将其放入队里头，而删除是直接
 * 去对列尾。
 */
public class LRU {
    private int capacity;
    private HashMap<Integer,Node> cache;
    private Node head;
    private Node tail;

    public LRU(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>(capacity);
    }

    public int get(int key) {
        if (capacity == 0) {
            return -1;
        }
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        recentUse(node);
        return node.getValue(key);
    }
     private void recentUse(Node node) {
        Node pre = node.getPre();
        Node next = node.getNext();
        if (pre == null) {
            return;
        }
        if (node != null) {
            next.setPre(pre);
        }
         pre.setNext(next);
         if (node == tail) {
             tail = pre;
         }
         node.setNext(head);
         node.setPre(null);
         head.setPre(node);
         head = node;
    }

    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        Node node = cache.get(key);
        if (node != null) {
            node.setValue(value);
            recentUse(node);
            return;
        }
        node = new Node(key, value);
        if (cache.size() == capacity) {
            cache.remove(tail.getKey());
            tail = tail.getPre();
            if (tail != null) {
                tail.setNext(null);
            }
        }
        cache.put(key, node);
        if (head != null) {
            head.setPre(node);
        }
        node.setNext(head);
        node.setPre(null);
        head = node;
        if (tail == null) {
            tail = node;
        }
    }
}
